package com.heziguo.sortAlgorithm;

import com.heziguo.entity.Student;
import com.heziguo.utils.SortHelper;

/**
 * 
 * @ClassName:  MergeSort 
 * @Package com.heziguo.sortAlgorithm    
 * @Description:归并排序
 * @author: 贺子国 
 * @date:   2018年8月10日 下午10:40:27   
 *     
 * @Copyright: 2018 www.heziguo.com Inc. All rights reserved. 
 * 注意：
 */
public class MergeSort {

	public static void main(String[] args) {
	/*	Integer[] list = { 2, 3, 2, 5, 6, 1, -2, 3, 14, 12,15,11 };
        mergeSort(list);
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }*/
        
       /* Integer [] arr = SortHelper.generateRandomArray(100, 0, 100);
        mergeSort2(arr);
		SortHelper.printArray(arr);*/
		
		 /*Integer [] arr = SortHelper.generateRandomArray(100, 0, 100);
	     mergeSort(arr);
	     SortHelper.printArray(arr);*/
		
		Student[] student = {new Student("A",100),new Student("C",80),new Student("D",50),new Student("B",90)};
		mergeSort(student);
		SortHelper.printArray(student);
		
		try {
			/*Integer [] arr = SortHelper.generateRandomArray(50000, 0, 50000);
			SortHelper.sortTime(SelectionSort.class, "selectintSort", Comparable[].class, arr);
			
			Integer [] arr2 = SortHelper.generateRandomArray(50000, 0, 50000);
			SortHelper.sortTime(InsertionSort.class, "insertionSort", Comparable[].class, arr);
			
			Integer [] arr3 = SortHelper.generateRandomArray(50000, 0, 50000);
			SortHelper.sortTime(MergeSort.class, "mergeSort", Comparable[].class, arr);*/
			
		} catch (Exception e) {
			// TODO Auto-generated catch block  
			e.printStackTrace();
		}
	}
	
	public static <T extends Comparable<? super T>> void mergeSort(T[] arr){
		mergeSort(arr,0,arr.length);
	}
	public static <T extends Comparable<? super T>> void mergeSort(T[] arr,int l,int r) {
		if (l>= r -1) {
			return;
		}
		int mid = (l+r)/2;		
		mergeSort(arr, l, mid);
		mergeSort(arr, mid, r);
		merge(arr,l,mid,r);
	}
	private static <T extends Comparable<? super T>> void merge(T[] arr, int l, int mid, int r) {
		T[] aux = (T[])new Comparable[r-l];
		System.arraycopy(arr, l, aux, 0, r-l);
		int i = 0, j = mid - l;
		for (int k = l; k < r; k++) {			
			if (i >= mid -l) {
				arr[k] = aux[j];
				j++;
			}else if (j >= aux.length) {
				arr[k] = aux[i];
				i++;
			}else if (aux[i].compareTo(aux[j]) > 0) {
				arr[k] = aux[i];
				i++;
			}else {
				arr[k] = aux[j];
				j++;
			}
		}		
	}


	/** 
     * 
     *  1 Comparable :
     * 返回类型 之前的 <E extends Comparable<E>> 相当于是基于  mergeSort(E[] list) 中确定的 E ，
     * 更进一步的限定信息，一同用来给编译器检验这个方法接受的参数是否符合 限定，
     * /
    /** The method for sorting the numbers */
    public static <E extends Comparable<E>> void mergeSort2(E[] list) {
        if (list.length > 1) {
            // Merge sort the first half
            E[] firstHalf = (E[]) new Comparable[list.length / 2];
            System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
            mergeSort2(firstHalf);

            // Merge sort the second half
            int secondHalfLength = list.length - list.length / 2;

            E[] secondHalf = (E[]) new Comparable[secondHalfLength];
            System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalfLength);
            mergeSort2(secondHalf);

            // Merge firstHalf with secondHalf
            E[] temp = merge(firstHalf, secondHalf);
            System.arraycopy(temp, 0, list, 0, temp.length);
        }
    }

    private static <E extends Comparable<E>> E[] merge(E[] list1, E[] list2) {
        E[] temp = (E[]) new Comparable[list1.length + list2.length];

        int current1 = 0; // Index in list1
        int current2 = 0; // Index in list2
        int current3 = 0; // Index in temp

        while (current1 < list1.length && current2 < list2.length) {
            if (list1[current1].compareTo(list2[current2]) < 0) {
                temp[current3++] = list1[current1++];
            } else {
                temp[current3++] = list2[current2++];
            }
        }

        while (current1 < list1.length) {
            temp[current3++] = list1[current1++];
        }

        while (current2 < list2.length) {
            temp[current3++] = list2[current2++];
        }

        return temp;
    }
}
